

#  二叉树

from collections import deque

class TreeNode():
    def __init__(self,value):
        self.element = value
        self.right = None
        self.left = None

class Tree():
    def __init__(self):
        self.root = None


    def add(self,value):
        node = TreeNode(value)
        if self.root == None:
            self.root = node
            return
        queue = deque()
        queue.append(self.root)
        while queue:
            cur = queue.popleft()
            if cur.left == None:
                cur.left = node
                return
            else:
                queue.append(cur.left)

            if cur.right == None:
                cur.right = node
                return
            else:
                queue.append(cur.right)


    def level_travel(self):
        if self.root == None:
            return []
        temp = []
        queue = deque()
        queue.append(self.root)
        while queue:
            cur = queue.popleft()
            temp.append(cur.element)
            if cur.left!=None:
                queue.append(cur.left)
            if cur.right!=None:
                queue.append(cur.right)
        print(temp)


    def preorder_travel(self,node):
        if node == None:
            return []
        print(node.element,end=" ")
        if node.left!=None:
            self.preorder_travel(node.left)
        if node.right!=None:
            self.preorder_travel(node.right)

    def inorder_travel(self,node):
        if node == None:
            return []
        if node.left!=None:
            self.inorder_travel(node.left)
        print(node.element,end=" ")
        if node.right!=None:
            self.inorder_travel(node.right)


    def postorder_travel(self,node):
        if node == None:
            return []
        if node.left!=None:
            self.inorder_travel(node.left)
        if node.right!=None:
            self.inorder_travel(node.right)
        print(node.element, end=" ")


if __name__ == "__main__":
    tree = Tree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.preorder_travel(tree.root)
    print()
    tree.level_travel()
    tree.inorder_travel(tree.root)
    print()
    tree.postorder_travel(tree.root)
    print()